/*	
 *				
 *					ISNW ---- It is a war.It is not warcraft!
 *
 *
 *					Author:					zhoukeli(haxixi_keli)
 *					Filename:				isnwArray.h
 *					CreateTime:				2008/12/06
 *					ModifyTime:				2008/12/06
 *
 */

#ifndef __ISNW_ARRAY_H__
#define __ISNW_ARRAY_H__

#include "isnwTypes.h"
#include "isnwAllocator.h"

namespace ISNW
{
namespace core
{
	template<typename T,class TAlloc = isnwAllocator<T> >
	class array
	{
	public:
		//! default constructor
		array():data(0),used(0),allocated(0){}

		//! destructor
		/** free all allocated memory.*/
		~array()
		{
			for(u32 i = 0; i < used; ++i)
				allocator.destruct(&data[i]);
			allocator.deallocate(data);
		}

		array(u32 start_count):data(0),used(0),allocated(start_count){}

		array(const array<T>& other)
		{
			*this = other;
		}

		T& operator [] (u32 idx)
		{
			if(idx < used)
			{
				return data[idx];
			}else
			{
				return data[0];
			}
		}

		const T& operator [] (u32 idx) const
		{
			if(idx < used)
			{
				return data[idx];
			}
			else
			{
				return data[0];
			}
		}

		void push_back(const T& element)
		{
			if(used+1 >= allocated)
			{
				// if element is in the same array, it is dangerous
				// grow(allocated*2+1) will free the element
				// so we copy it first to avoid memory corruption
				T e(element);
				grow(allocated*2+1);

				allocator.construct(&data[used++],e);
			}else
			{
				allocator.construct(&data[used++],element);
			}
		}

// 		template<typename B>
// 		void clone(array<B> out)
// 		{
// 			out.set_used(used);
// 
// 			for(u32 i = 0; i < used; ++i)
// 			{
// 				out[i] = (B)(data[i]);
// 			}
// 
// 			return;
// 		}

		void erase(u32 idx)
		{
			if(idx >= used)
				return;

			for(u32 i = idx; i < used-1; ++i)
			{
				allocator.destruct(&data[i]);
				allocator.construct(&data[i],data[i+1]);
			}

			allocator.destruct(&data[used-1]);
			
			--used;
		}

		void erase(u32 idx,s32 cnt)
		{
			if(idx+cnt > used || cnt < 1)
			{
				return;
			}

			u32 i = idx;
			u32 j = idx + cnt;

			while(j < used)
			{
				allocator.destruct(&data[i]);
				allocator.construct(&data[i],data[j]);
				++i,++j;
			}
			while(i < used)
			{
				allocator.destruct(&data[i]);
				++i;
			}
			used--;
			if(used < allocated * 0.3)
			{
				attenuate(used*2);
			}
		}

		bool empty()
		{
			return (used == 0);
		}

		u32 allocated_size()
		{
			return allocated;
		}

		u32 size() const
		{
			return used;
		}

		T* pointer()
		{
			return data;
		}

		T& getlast()
		{
			return data[used-1];
		}

		void set_used(u32 u)
		{
			if(u > allocated)
			{
				grow(u);
			}
			else if(u < allocated)
			{
				attenuate(u);
			}

			used = u;
		}

		void clear()
		{
			for(u32 i = 0; i < used; ++i)
			{
				allocator.destruct(&data[i]);
			}

			allocator.deallocate(data);
			
			data = 0;
			used = allocated = 0;
		}

		s32 find(T e)
		{
			for(u32 i = 0; i < used; ++i)
			{
				if(data[i] == e) return i;
			}

			return -1;
		}

		array<T>& operator = (const array<T>& other)
		{
			if(data)
			{
				for(u32 i = 0; i < used; ++i)
				{
					allocator.destruct(&data[i]);
				}

				allocator.deallocate(data);

				data = 0;

				allocator = used = (T)0;
			}

			if(other.used > 0)
			{
				grow(other.allocated);
				for(u32 j = 0; j < other.used; ++j)
				{
					allocator.construct(&data[j],other.data[j]);
				}

				used = other.used;
				allocated = other.allocated;
			}
		}

		bool operator == (const array<T>& other)
		{
			if(used != other.used || allocated != other.allocated)
				return false;

			for(u32 i = 0; i < used; ++i)
			{
				if(data[i] != other.data[i])
					return false;
			}

			return true;
		}

		bool operator != (const array<T>& other)
		{
			return !(*this == other);
		}

	protected:
		//! grow bigger
		void grow(size_t cnt)
		{
			// never grow smaller
			if(cnt <= allocated)
				return;

			T* old_data = data;

			data = allocator.allocate(cnt);

			for(u32 i = 0; i < used; ++i)
			{
				// data[i] = old_data[i]
				allocator.construct(&data[i],old_data[i]);
			}

			// destruct old data
			for(u32 j = 0; j < used; ++j)
			{
				allocator.destruct(&old_data[j]);
			}

			allocator.deallocate(old_data);	// delete[] old_data

			allocated = cnt;
		}

		//! attenuate smaller
		void attenuate(size_t cnt)
		{
			// never attenuate to be bigger
			if(cnt >= allocated)
				return;

			T* old_data = data;
			data = allocator.allocate(cnt);

			for(u32 i = 0; i < cnt; ++i)
			{
				// data[i] = old_data[i]
				allocator.construct(&data[i],old_data[i]);
			}

			// destruct old data
			for(u32 j = 0; j < used; ++j)
			{
				allocator.destruct(&old_data[j]);
			}

			allocator.deallocate(old_data); // delete[] old_data

			allocated = cnt;
			if(used > cnt)
				used = cnt;
		}

	protected:
		T*				data;
		u32				used;
		u32				allocated;
		TAlloc			allocator;
	};
} // end namespace core
} // end namespace ISNW
#endif